package com.flying.srccode;

import org.junit.jupiter.api.Test;

import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

/**
 * @ClassName HashMapSrc
 * @Author flying
 * @Date 2025/2/3 8:34
 * @Description HashMap源码分析
 */
public class HashMapSrc {

    /**
     * 底层存储分析
     * HashMap底层实现采用了哈希表，这是一种非常重要的数据结构。对于我们以后理解很多技术都非常有帮助。
     * <p>
     * 数据结构中由数组和链表来实现对数据的存储，他们各有特点。
     * <p>
     * (1) 数组：占用空间连续。 寻址容易，查询速度快。但是，增加和删除效率非常低。
     * <p>
     * (2) 链表：占用空间不连续。 寻址困难，查询速度慢。但是，增加和删除效率非常高。
     * <p>
     * 那么，我们能不能结合数组和链表的优点（即查询快，增删效率也高）呢？ 答案就是“哈希表”。 哈希表的本质就是“数组+链表
     */
    @Test
    void test1() {

        /**  单向链表节点类
         *     static class Node<K,V> implements Map.Entry<K,V> {
         *         final int hash;
         *         final K key;
         *         V value;
         *         Node<K,V> next;
         *
         *         Node(int hash, K key, V value, Node<K,V> next) {
         *             this.hash = hash;
         *             this.key = key;
         *             this.value = value;
         *             this.next = next;
         *         }
         *
         *         public final K getKey()        { return key; }
         *         public final V getValue()      { return value; }
         *         public final String toString() { return key + "=" + value; }
         *
         *         public final int hashCode() {
         *             return Objects.hashCode(key) ^ Objects.hashCode(value);
         *         }
         *
         *         public final V setValue(V newValue) {
         *             V oldValue = value;
         *             value = newValue;
         *             return oldValue;
         *         }
         *
         *         public final boolean equals(Object o) {
         *             if (o == this)
         *                 return true;
         *
         *             return o instanceof Map.Entry<?, ?> e
         *                     && Objects.equals(key, e.getKey())
         *                     && Objects.equals(value, e.getValue());
         *         }
         *     }
         *
         *     红黑树节点类
         *      static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
         *         TreeNode<K,V> parent;  // red-black tree links
         *         TreeNode<K,V> left;
         *         TreeNode<K,V> right;
         *         TreeNode<K,V> prev;    // needed to unlink next upon deletion
         *         boolean red;}
         */

        /**
         * 1. 哈希表的数组长度大于64，并且单项链表的长度大于8时，整个链表会被转换为红黑树
         * 2. 当红黑树的节点数通过删除操作，树节点减少到6时，红黑树会被转换为链表
         */
        HashMap<String, Integer> map = new HashMap<>();

    }


    /**
     * HashMap的成员变量
     */
    @Test
    void test2(){
        HashMap<String, Integer> map = new HashMap<>();


        /**
         * 默认的初始容量（桶/数组大小）；必须是2的次幂
         * static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
         *
         * 允许的最大容量，值为 2^30（约10.7亿）；防止内存溢出，容量超过此值时不再扩容。
         * static final int MAXIMUM_CAPACITY = 1 << 30;
         *
         * 默认的加载因子，值为 0.75；权衡时间与空间效率。较小的值减少冲突但浪费空间；较大的值增加冲突但节省空间。
         * static final float DEFAULT_LOAD_FACTOR = 0.75f;
         *
         * 链表转为红黑树的阈值，当链表长度 ≥8 时触发树化。
         * static final int TREEIFY_THRESHOLD = 8;
         *
         * 红黑树退化为链表的阈值，当树节点数 ≤6 时触发退化。
         * static final int UNTREEIFY_THRESHOLD = 6;
         *
         * 允许树化的最小桶数量，值为 64。当桶数量小于64时，优先扩容而非树化（避免小容量下频繁树化）
         * static final int MIN_TREEIFY_CAPACITY = 64;
         *
         * 存储键值对的数组（桶数组）；每个元素是链表或红黑树的头节点
         * transient Node<K,V>[] table;
         *
         * transient Set<Map.Entry<K,V>> entrySet;
         *
         *  记录当前HashMap中的键值对数量。插入时递增，删除时递减，用于判断是否需要扩容
         *  transient int size;
         *
         *  transient int modCount;
         *
         * 扩容阈值，当HashMap中的键值对个数（size） > threshold时触发扩容；初始值为capacity * loadFactor，扩容后重新计算
         *  int threshold;
         *
         *  final float loadFactor; （ this.loadFactor = DEFAULT_LOAD_FACTOR;）
         */





    }

    /**
     * HashMap计算哈希值
     */
    @Test
    void test3() {
        // 1. this.loadFactor = DEFAULT_LOAD_FACTOR  0.75
        HashMap<String,Integer> map=new HashMap<>();

        //  putVal(hash(key), key, value, false, true);
        map.put("a",11);


        /**
         * 位运算复习
         * &	按位与（AND）	两位同时为 1 时结果为 1，否则为 0。
         * |	按位或（OR）	两位中至少一个为 1 时结果为 1，否则为 0。
         * ^	按位异或（XOR）	两位不同时为 1，相同时为 0。
         * ~	按位非（NOT）	单目运算符，对每一位取反（0 变 1，1 变 0）。
         * <<	左移（Left Shift）	将二进制位向左移动指定位数，右侧补 0。
         * >>	右移（Right Shift）	将二进制位向右移动指定位数，左侧补符号位（正数补 0，负数补 1）。
         * >>>	无符号右移	将二进制位向右移动指定位数，左侧补 0（无论正负）。
         */

        /**  计算 key哈希值
         *
         *     static final int hash(Object key) {
         *         int h;
         *         return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
         *     }
         *
         *     获取key的hashcode值并与key的前16位做异或运算（相同为0，不同为1）
         *     key的hashcode为 123456
         *     0000 0000 0000 0001 1110 0010 0100 0000
         *     0000 0000 0000 0000 0000 0000 0000 0001
         *     0000 0000 0000 0001 1110 0010 0100 0001   hash(key)返回值  123457
         *
         *     `(p = tab[i = (n - 1) & hash]` -- n代表桶的长度，首次初始化长度为16
         *     哈希值： key经过hash()方法的计算后与桶的最大索引 做 & 运算的结果
         */



    }

    /**
     * 数组初始化（桶初始化），延迟初始化。并不是在HashMap创建时就初始化哈希表。而是在第一次
     * 添加元素时，初始化数组
     */
    @Test
    void test4(){
        /**
         * final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
         *                    boolean evict) {
         *         Node<K,V>[] tab; Node<K,V> p; int n, i;
         *         if ((tab = table) == null || (n = tab.length) == 0)
         *             TODO: n = (tab = resize()).length;
         *             .....
         *      resize() <|
         *         else {
         *         // zero initial threshold signifies using defaults
         *             newCap = DEFAULT_INITIAL_CAPACITY;   // 16
         *             newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // 0.75*16 当HashMap中的键值对达到阈值是，进行数组扩容
         *         }
         *
         *         threshold = newThr;
         *         Node<K, V>[] newTab = (Node<K,V>[])new Node[newCap];
         *         table = newTab;
         *         ......
         *         return newTab;
         *
         *         这样就得到了 一个长度为16的数组
         */

    }


    /**
     * 添加元素
     */
    @Test
    void test5(){
        // 1. 指定加载因子 ： 0.74 (哈希表达到阈值是会进行扩容，阈值计算方法： 容量*加载因子)
        HashMap<String,Integer> map=new HashMap<>();

        /**
         * 1. 通过hash(key)特定的方法，计算出key的"哈希值"(return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);)
         * 2. 调用 putVal()方法进行元素的添加
         *   putVal(hash(key), key, value, false, true);
         *   2.1 初始化数组，调用 resize()方法
         *   2.2  进行元素的添加
         *      2.2.1 通过 (n - 1) & hash 算法得出元素在哈希表中数组的索引。 n代表桶的长度
         *      2.2.2 进行元素添加
         *        第一种情况： 无相同哈希值的key：直接在桶中添加元素
         *                  tab[i] = newNode(hash, key, value, null);
         *        第二种情况： 桶中有相同哈希值的节点
         *              2.1   有相同的哈希值且key的值相同：
         *                       if (p.hash == hash &&
         *                      ((k = p.key) == key || (key != null && key.equals(k))))
         *                      e = p;   // 将老的节点赋值给 新节点 e（后续在进行操作）
         *              2.2  判断相同哈希值的节点是不是 TreeNode类型的树节点，则进行树形节点的添加操作
         *                   e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
         *              2.3  遍历链表，查找最后一个节点（JDK8及以后版本中，总是在链表的末尾添加节点）
         *                   进行节点的挂接操作  :  p.next = newNode(hash, key, value, null);
         *                   进行链表与红黑树的转换阈值判断： if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st  0  1 2 3 4 5 6 7  --> 8个节点
         *                                                  treeifyBin(tab, hash);
         *                                              break;
         *                                              同时需要满足数组和长度大于 64 ,才会将链表树化
         *
         *
         *              循环开始（binCount=0）
         *                 ↓
         *              检查 p.next 是否为 null
         *                 ↓
         *              是 → 创建新节点插入链表尾部
         *                      ↓
         *                      检查 binCount >= 7？
         *                         ↓
         *                         是 → 调用 treeifyBin 树化
         *                 ↓
         *              否 → 检查键是否重复
         *                      ↓
         *                      是 → 退出循环，覆盖旧值
         *                      ↓
         *                      否 → p = e，继续遍历
         *
         */
        map.put("a",11);

    }

    /**
     *  数组扩容
     */
    @Test
    void test6(){
        /**
         * 当链表的节点树达到阈值 8个时，会调用treeifyBin()方法进行链表树化还是数组扩容的判断及下一步操作
         * if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
         *   treeifyBin(tab, hash)
         *
         *
         *      if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
         *        resize();
         *
         *   数组扩容核心方法
         *   resize():
         *   1. 定义了局部变量
         *      Node<K,V>[] oldTab = table;    // 旧数组
         *      int- oldCap = (oldTab = null) ? 0 : oldTab.Length;    // 旧数组的容量
         *      int oldThr = threshold;                               // 旧数组的扩容阈值
         *      int newcap, newThr = 0；  // 新容量和扩容阈值
         *   2. 通过2个if分支语句计算新容量和阈值
         *          if (oldCap > 0) { // 第一个分支此种情况，代表不是第一次初始化数组
         *          // 旧数组长度大于最大长度64，将扩容阈值设为最大整数，并将旧数组返回，供后续链表树化操作
         *             if (oldCap >= MAXIMUM_CAPACITY) {
         *                 threshold = Integer.MAX_VALUE;
         *                 将 threshold 设为 Integer.MAX_VALUE 是 HashMap 在容量达到上限时的保护性措施：
         *                  > 阻止扩容导致的整数溢出和内存问题。
         *                  > 允许用户继续插入数据（尽管性能下降）。
         *                  > 符合 Java 集合框架的健壮性设计原则。
         *                 return oldTab;
         *             }
         *             else if ((newCap = oldCap << 1(新容量扩容为2倍)) < MAXIMUM_CAPACITY(64) &&
         *                      oldCap >= DEFAULT_INITIAL_CAPACITY(16))
         *                 newThr = oldThr << 1; // double threshold
         *         }
         *         else if (oldThr > 0) //
         *         // 通过 HashMap(int initialCapacity) 构造函数,接收用户指定的初始容量，将容量暂时用threshold保存，
         *         等到第一次添加元素时,根据 newCap 和加载因子（loadFactor）计算新的 threshold
         *             newCap = oldThr;
         *         else {
         *         // zero initial threshold signifies using defaults
         *         // 此种情况表示并未进行数组的初始化
         *             newCap = DEFAULT_INITIAL_CAPACITY; （默认容量16）
         *             newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); 0.75*16
         *         }
         *         if (newThr == 0) {
         *         为什么需要检查 newThr == 0
         *              在上述分支中，存在一些情况会导致 newThr 没有被正确赋值，仍然为 0：
         *          旧阈值大于 0 的情况：
                                    当进入 else if (oldThr > 0) 分支时，只设置了 newCap，没有设置 newThr，所以 newThr 保持为 0。
         *          其他未覆盖的特殊情况：
         *                          虽然代码逻辑已经考虑了大部分常见情况，但为了保证代码的健壮性，即使出现一些意外情况导致 newThr 为 0，
         *                  也能通过最后的检查来计算出一个合理的新阈值。
         *                  因此，最后添加 if (newThr == 0) 的检查，根据新容量 newCap 和负载因子 loadFactor 重新计算新阈值，
         *                  确保 newThr 有一个合理的值，避免在后续使用中出现阈值为 0 导致的异常情况。
         *             float ft = (float)newCap * loadFactor;
         *             newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
         *                       (int)ft : Integer.MAX_VALUE);
         *         }
         *
         *         进行成员变量的更新：
         *         threshold = newThr;
         *         @SuppressWarnings({"rawtypes","unchecked"})
         *         Node<K, V>[] newTab = (Node<K,V>[])new Node[newCap];
         *         table = newTab;
         *         if (oldTab != null) {
         *               // 进行元素移动，将旧桶中的元素移动到新桶中
         *         }
         *
         *          return  newTab ;  最后返回扩容后的数组
         */

    }

}
